package main.leetcode.clockin.April;

import java.util.Arrays;

/**
 * 面试题16.03.交点
 *
 * <p>给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。
 *
 * <p>要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。
 *
 * <p>
 *
 * <p>示例 1：输入： line1 = {0, 0}, {1, 0} line2 = {1, 1}, {0, -1} 输出： {0.5, 0}
 *
 * <p>示例 2：输入： line1 = {0, 0}, {3, 3} line2 = {1, 1}, {2, 2} 输出： {1, 1}
 *
 * <p>示例 3：输入： line1 = {0, 0}, {1, 1} line2 = {1, 0}, {2, 1} 输出： {}，两条线段没有交点
 *
 * <p>提示：坐标绝对值不会超过 2^7 输入的坐标均是有效的二维坐标
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day12 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        new day12()
                                .intersection(
                                        new int[] {-10, 48},
                                        new int[] {-43, 46},
                                        new int[] {-16, 59},
                                        new int[] {-1, 85})));
        System.out.println(
                Arrays.toString(
                        new day12()
                                .intersection(
                                        new int[] {0, 0},
                                        new int[] {1, 0},
                                        new int[] {1, 1},
                                        new int[] {0, -1})));
        System.out.println(
                Arrays.toString(
                        new day12()
                                .intersection(
                                        new int[] {0, 0},
                                        new int[] {3, 3},
                                        new int[] {1, 1},
                                        new int[] {2, 2})));
        System.out.println(
                Arrays.toString(
                        new day12()
                                .intersection(
                                        new int[] {0, 1},
                                        new int[] {0, 1},
                                        new int[] {0, 0},
                                        new int[] {0, -1})));
        System.out.println(
                Arrays.toString(
                        new day12()
                                .intersection(
                                        new int[] {1, 0},
                                        new int[] {1, 1},
                                        new int[] {-1, 0},
                                        new int[] {3, 2})));
    }

    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        int x1 = start1[0];
        int y1 = start1[1];
        int x2 = end1[0];
        int y2 = end1[1];

        int x3 = start2[0];
        int y3 = start2[1];
        int x4 = end2[0];
        int y4 = end2[1];

        // 双垂线
        if (x1 == x2 && x3 == x4) {
            if (x1 != x3) return new double[] {};
            return doublyVertical(x1, y1, y2, y3, y4);
        }
        // 单垂线
        else if (x1 == x2) {
            return singleVertical(x1, y1, y2, x3, y3, x4, y4);
        }
        // 单垂线
        else if (x3 == x4) {
            return singleVertical(x3, y3, y4, x1, y1, x2, y2);
        }

        double k1 = ((double) end1[1] - start1[1]) / (end1[0] - start1[0]);
        double k2 = ((double) end2[1] - start2[1]) / (end2[0] - start2[0]);
        double b1 = start1[1] - k1 * start1[0];
        double b2 = start2[1] - k2 * start2[0];
        // 斜率相同
        if (k1 - k2 == 0) {
            // 不重合
            if (b1 - b2 != 0) return new double[] {};
            // 重合
            return overlap(k1, b1, x1, y1, x2, y2, x3, y3, x4, y4);
        }

        double x = (b2 - b1) / (k1 - k2);
        double y = k1 * x + b1;
        int minX1, maxX1;
        if (x1 < x2) {
            minX1 = x1;
            maxX1 = x2;
        } else {
            maxX1 = x1;
            minX1 = x2;
        }
        int minX2, maxX2;
        if (x3 < x4) {
            minX2 = x3;
            maxX2 = x4;
        } else {
            maxX2 = x3;
            minX2 = x4;
        }
        // 交点不在线段上
        if (x < Math.max(minX1, minX2) || x > Math.min(maxX1, maxX2)) return new double[] {};
        return new double[] {x, y};
    }

    private double[] overlap(
            double k, double b, int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
        int minX1, maxX1;
        if (x1 < x2) {
            minX1 = x1;
            maxX1 = x2;
        } else {
            maxX1 = x1;
            minX1 = x2;
        }
        if (minX1 > x3 && minX1 > x4 || maxX1 < x3 && maxX1 < x4) return new double[] {};

        int minX2 = Math.min(x3, x4);
        if (minX1 < minX2) return new double[] {minX2, k * minX2 + b};
        return new double[] {minX1, k * minX1 + b};
    }

    private double[] singleVertical(int x, int y1, int y2, int x3, int y3, int x4, int y4) {
        double k = ((double) y4 - y3) / (x4 - x3);
        double b = y4 - k * x4;
        double y = k * x + b;
        if (y < y1 && y < y2 || y > y1 && y > y2) return new double[] {};
        return new double[] {x, y};
    }

    private double[] doublyVertical(int x, int y1, int y2, int y3, int y4) {
        int minY1, maxY1;
        if (y1 < y2) {
            minY1 = y1;
            maxY1 = y2;
        } else {
            minY1 = y2;
            maxY1 = y1;
        }
        if (maxY1 < y3 && maxY1 < y4 || minY1 > y3 && minY1 > y4) return new double[] {};
        else {
            int y = Math.max(minY1, Math.min(y3, y4));
            return new double[] {x, y};
        }
    }
}
